class code1 {
    //首先尝试dp[i]:以i位置为结尾的所有子序列中，最长的斐波那契子序列的长度-> but不知道前后位置斐波那契的值
    //dp[i][j]：以i位置和j位置结尾的所有子序列中，最长的斐波那契子序列的长度
    //方程式推导-> 三个数[对应下标]：a[k] b[i] c[j]  a = c-b
    //1） a存在，并且a<b    ->dp=dp[k][i]+1
    //2） a存在，but b<a<c ->dp=2
    //3） a不存在           ->dp=2

    //Q：怎么找k值（第一个数的下标）？->hash
    public int lenLongestFibSubseq(int[] arr) {
        int n = arr.length;

        int[][] dp = new int[n][n];
        int ret = 0;

        Map<Integer,Integer> hash =  new HashMap<Integer,Integer>();
        //为了找第一个值
        for(int i=0;i<n;i++) {
            hash.put(arr[i],i);
        }
        //初始化
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                dp[i][j] = 2;//默认最后两个数已经找到
            }
        }
        for(int j=2;j<n;j++) {//对应最后一个数
            for(int i=1;i<j;i++) {//对应倒数第二个数
                int a = arr[j]-arr[i];
                if(hash.containsKey(a) && a<arr[i]) {
                    dp[i][j] = dp[hash.get(a)][i] + 1;
                    ret = Math.max(ret,dp[i][j]);
                }
            }
        }

        return ret<3?0:ret;
    }
}